#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

/* 模拟PR进程调度算法 */

// PCB结构体
typedef struct node{
  char name[10];
  int prio;
  int cputime;
  int needtime;
  char state;  // R:运行 W:就绪 F:完成
  struct node *next;
} PCB;

PCB *finish,*ready,*run;
int N;

void printPCB(PCB *q)
{
  printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);
}

void print()
{
  PCB *p;
  printf("进程号  cpu时间   所需时间  优先数   状态\n");
  
  // 正在运行
  if(run != NULL)
    printPCB(run);
  // 就绪队列
  p = ready;
  while(p != NULL)
  {
    printPCB(p);
    p = p->next;
  }
  // 完成队列
  p = finish;
  while(p != NULL)
  {
    printPCB(p);
    p = p->next;
  }

  printf("按任意键继续...\n");
  getchar();
}

PCB* selectNextProcess() {
    if(ready == NULL) return NULL;
    PCB *selected = ready;
    ready = ready->next;
    selected->next = NULL;
    return selected;    
}

void insert(PCB *q)
{
    if(ready == NULL){
	ready = q;
	q->next = NULL;
	return;
    }
    PCB *current = ready;
    PCB *prev = NULL;
    
    while(current != NULL && current->prio <= q-> prio){
	prev = current;
	current = current->next;
    }
    if(prev == NULL){
	q->next = ready;
	ready = q;
    }
    else{
	prev->next = q;
	q->next = current;
    }  
}

void CPUTicks()
{
  if(run != NULL)
  {
    run->cputime += 1;
    run->needtime -= 1;
    if(run->needtime == 0)
    {
      run->state = 'F';
      run->next = finish;
      finish = run;
      run = NULL;
    }
  }
}

void runScheduler() // 进程调度算法
{  
  while(ready != NULL)
  {
    // 根据优先级选择下一个要运行的进程
    run = selectNextProcess();
    
    if (run == NULL) break;
    
    run->state = 'R';
    
    // 运行进程直到完成
    while(run != NULL && run->needtime > 0)
    {
      print();
      CPUTicks();
    }
    
    // 进程现在已经完成或为空
  }
}

int main()
{
  PCB *p;
  int i, time,prio;
  char na[10];
  
  printf("输入进程数: ");
  scanf("%d",&N);
  
  // 初始化队列
  ready = NULL;
  finish = NULL;
  run = NULL;
  
  // 创建进程并添加到就绪队列
  for(i = 1; i <= N; i++)
  {
    p = (PCB *)malloc(sizeof(PCB));
    printf("输入第%d个进程名: ",i);
    scanf("%s",na);
    printf("输入第%d个进程所需时间: ",i);
    scanf("%d",&time);
    printf("输入第%d个进程优先级：",i);
    scanf("%d",&prio);

    strcpy(p->name,na);
    p->cputime = 0;
    p->needtime = time;
    p->state = 'W';
    p->prio = prio;
    insert(p);
  }
  
  printf("PR算法:\n");
  printf("*****************************************\n");
  getchar();
  
  runScheduler();
  
  print();
  printf("进程调度完成\n");
  printf("按任意键退出...\n");
  getchar();
  return 0;
}
